Wirusy

Limit pamięci: 32 MB

Mamy daną tablicę o rozmiarach , których komórki indeksujemy parami liczb całkowitych , . Z początku komórki są puste, ale z czasem pojawiają się na niej wirusy różnych rodzajów i zaczynają się rozmnażać. Każdy wirus ma określony czas pojawienia jako dzień i godzinę, oraz miejsce pojawienia jako współrzędne komórki. Następnie wirus każdego dnia o zadanej godzinie (tej samej, w której się po raz pierwszy pojawił) aktywuje się i replikuje się. Replikacja polega na zajęciu wszystkich wolnych komórek, które sąsiadują z wirusem danego rodzaju. Komórki i są sąsiadujące, jeżeli . Wirusy replikują się tak długo, aż zajmą całą tablicę. Wirus może się w ogóle nie pojawić w przypadku, gdy miejsce pojawienia się jest już zajęte przez innego wirusa.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis wirusów,
• dla każdego wirusa wyznaczy liczbę zajętych komórek,
• zapisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite i oddzielone pojedynczym odstępem, , . Każdy z następnych wierszy zawiera cztery liczby całkowite , , i , , , pooddzielanych pojedynczymi odstępami, oznaczające odpowiednio godzinę, dzień i współrzędne pojawienia się wirusa. Można założyć, że nie istnieją dwa wirusy o tej samej godzinie pojawienia się, tzn. wartość parametru nie powtórzy się na wejściu.

Wyjście

Wyjście powinno składać się z liczb całkowitych w osobnych wierszach oznaczających liczbę zajętych komórek przez poszczególne wirusy.

Przykład

Do czytelniejszego przedstawienia przykładowego wejścia i wyjścia zostały użyte kolorowe czcionki.

Dla danych wejściowych:

5 4
1 2 4 4
2 1 5 1
0 3 1 3
3 3 3 3

poprawną odpowiedzią jest:

10
7
8
0

Dla każdej komórki, kolor oznacza wirusa, który ją zajął, a liczba oznacza dzień, w którym została zajęta dana komórka. Komórka o współrzędnych jest w lewym dolnym rogu.

Autor zadania: Jakub Pawlewicz.